// Copyright (C) 2010 and onwards Noam Shazeer and Georges Harik
// Pieces of this code may be licenced under the Apache License, version 2.0 
//   from Harik Shazeer Labs

#ifndef _THING_H_
#define _THING_H_

#include "util.h"

struct CollisionException {};

// For indirect types:
//    keep a hash table from their ContentHash to their Box*
extern uint64 G_BOX_INDEX_SPACE, G_BOX_INDEX_MASK;

// low 3 bits determines Basic Type
enum ThingType {
  // BASIC BOXED TYPES
  DIRECT_ARRAY,  // Needs to be BasicType 0 - may be an ARRAY or MARRAY
  INDIRECT_ARRAY,
  SYMBOL,             // User defined symbols. Never Direct.
  UNKNOWN_BOXED,

  // BASIC UNBOXED TYPES
  INTEGER,            // 61 bit signed
  DOUBLE,
  SPECIAL,           // special forms like IF DOTIMES
  UNKNOWN_UNBOXED, 

  // EXTENDED BOXED TYPES
  FREE_SPACE,
  MUTABLE_ARRAY,
  IMMUTABLE_ARRAY,

  // EXTENDED UNBOXED TYPES
  CHAR,              // 8 bit characters
  SYSCALL,
  NATIVE_FUNCTION,   // +, -, etc.
  TOKEN,
};

// Use this value for all nans.  Non-signaling positive nan with no payload. 
const uint64 MY_NAN = 0x7FF8000000000000ull + DOUBLE;

struct Box; // forward declaration for Thing

struct Thing {
  // Names for some unboxed things
  static map<string, Thing> string_thing_;
  static map<Thing , string> thing_string_;
  
  uint64 data_;

  Thing() {}
  Thing(uint64 i) : data_(i) {}

  void operator= (uint64 i) { data_ = i; }
  bool operator==(const Thing & o) const {
    return (ID() == o.ID()); }
  bool operator!=(const Thing & o) const {
    return !(ID() == o.ID()); }
  bool operator <(const Thing & o) const {
    return (ID() < o.ID()); }
  // bool operator!() { return !data_; }
  // operator bool() { return data_; }

  uint64 ID() const {
    if (data_ == 0) return 0;
    ThingType tt = GetBasicType();
    if (tt != DIRECT_ARRAY) return data_;
    return DirectArrayID();
  }
  uint64 DirectArrayID() const;

  ThingType GetBasicType() const { return (ThingType) (data_ & 0x7); }
  ThingType GetType() const;

  // Getting at the value of the thing
  Box * MaybeGetBox() const;
  Box * GetBox() const;
  uint64 GetUnboxedValue() const { return data_ >> 16; }
  Box ** GetBoxPointerPointer() const; // used for indirect things
  int64 GetInteger() const { return ((int64) data_) >> 3; }
  double GetDouble() const { 
    switch (GetBasicType()) {
    case INTEGER:
      return GetInteger();
    case DOUBLE: {
      uint64 bits = data_ & ~0x7ull;
      return *(reinterpret_cast<double *>(&bits));
    }
    default:
      CHECK(false);
      return 0;
    }
  }
  uchar GetChar() const { return GetUnboxedValue(); }  
  
  // Some quick checks on things
  bool Is() const { return data_; }
  bool IsNot() const { return !data_; }
  bool IsDirect() const { return (GetBasicType() == DIRECT_ARRAY); }
  bool IsIndirect() const { return IsBoxed() && !IsDirect(); }
  bool IsUnboxed() const { return (GetBasicType() > UNKNOWN_BOXED); }
  bool IsBoxed() const { return !IsUnboxed(); }
  bool IsInteger() const { return (GetBasicType() == INTEGER); }
  bool IsDouble() const { return (GetBasicType() == DOUBLE); }
  bool IsNumber() const { return (GetBasicType() == INTEGER || 
				  GetBasicType() == DOUBLE); } 
  bool IsArray() const { 
    return (GetBasicType() == DIRECT_ARRAY) 
      || (GetBasicType() == INDIRECT_ARRAY); }
  bool IsChar() const { return (GetType() == CHAR); }
  bool IsSyscall() const { return (GetType() == SYSCALL); }
  bool IsSymbol() const { return (GetBasicType() == SYMBOL); }
  bool IsToken() const { return (GetType() == TOKEN); } 
  bool IsMutable() const { return (GetType() == MUTABLE_ARRAY); }
  bool IsString() const; // An array containing only CHARs

  // Forwarding to boxes to deal with arrays
  uint64 ArraySize() const; 
  Thing & Ref(int i); // works for both mutable and immutable arrays.
  uint64 NodeCount() const;

  // -----  Making Things ------
  static uint64 MakeID(ThingType basic_type, uint64 content_hash) {
    return (basic_type | (content_hash & ~0x7ull)); }
  static uint64 MakeArrayID(Thing *contents, uint64 length);
  static uint64 MakeArrayID2(Thing t0, Thing t1) {
    Thing buf[2]; buf[0] = t0; buf[1] = t1; 
    return MakeArrayID(buf, 2); }
  static uint64 MakeArrayID3(Thing t0, Thing t1, Thing t2) {
    Thing buf[3]; buf[0] = t0; buf[1] = t1; buf[2] = t2; 
    return MakeArrayID(buf, 3); }
  static uint64 MakeArrayID4(Thing t0, Thing t1, Thing t2, Thing t3) {
    Thing buf[4]; buf[0] = t0; buf[1] = t1; buf[2] = t2; buf[3] = t3; 
    return MakeArrayID(buf, 4); }
  static uint64 MakeArrayID5(Thing t0, Thing t1, Thing t2, Thing t3, Thing t4) {
    Thing buf[5]; buf[0] = t0; buf[1] = t1; buf[2] = t2; buf[3] = t3; buf[4]= t4;
    return MakeArrayID(buf, 5); }

  // Making unboxed things
  static Thing BindUnboxed(ThingType t, int value, string name);
  static Thing NameToUnboxedThing(string name);

  static Thing MakeSpecial(string name);
  static Thing MakeKnownUnboxed(ThingType type, uint64 value) {
    return (Thing) ((value << 16) + type); }
  static Thing MakeUnknownUnboxed(ThingType type, uint64 value) {
    return (Thing) ((type << 8) + (value << 16) + UNKNOWN_UNBOXED); }
  static Thing MakeUnboxed(ThingType type, uint64 value) {
    return (type > UNKNOWN_UNBOXED) ? 
      MakeUnknownUnboxed(type, value) : MakeKnownUnboxed(type, value); }
  static Thing MakeCharacter(uchar c) {
    return MakeUnknownUnboxed(CHAR, c); }
  static Thing MakeInteger(int64 i) {
    return (Thing)((i << 3) + INTEGER); }
  static Thing MakeDouble(double d) {
    // always use the same nan.
    if (isnan(d)) return (Thing)MY_NAN;
    // round to nearest, ties away from 0.
    return 
      (Thing)(((*(reinterpret_cast<uint64 *>(&d)) + 4) & ~0x7ull) + DOUBLE);
  }
  static Thing MakeToken(int64 i) {
    return MakeUnknownUnboxed(TOKEN, i); }
};

// We need this for globals
struct ThingHash {
  size_t operator() (Thing t) const { return (size_t) t.data_; }
};

extern Box ** G_BOX_INDEX;

// flags in info_
const uint64 FLAG_KEEP = 0x100;

// Boxed objects: Arrays or Byte Arrays
struct Box {
  // info_: (least sig.)0:type 1:flags 2:lg_2(access_count) 3-7 length
  uint64 info_;
  uint64 id_;
  Box * link_; // for garbage collection
  #define marray_data__ link_
  uint64 node_count_; // for immutable arrays. 0 is >= 2^60
  #define marray_capacity__ node_count_

  Box() { CHECK(false); } // Don't construct Boxes. They are allocated.

  uint64 WordSize() {
    switch(GetType()) {
    case IMMUTABLE_ARRAY:
    case SYMBOL:
      return (sizeof(Box) / sizeof(uint64)) + GetLength();
    case FREE_SPACE:
      return GetLength();
    case MUTABLE_ARRAY: // Should never need to do this
    default:
      CHECK(false); return 0;
    }
  }

  Box * Next() { return (Box *) (( (uint64 *) this) + WordSize()); }

  // Insert into indirect Index. Return the number of steps of resolution
  uint64 Index();

  // accessors
  void ZeroOut() { info_ = 0; id_ = 0; link_ = NULL; node_count_ = 0; }
  ThingType GetType() const { return ThingType(info_ & 0xff); }
  void SetType(uchar type) 
  { info_ = (info_ & 0xffffffffffffff00ull) | type; }
  bool GetFlag(uint64 flag) { return info_ & flag; }
  void SetFlag(uint64 flag) { info_ |= flag; }
  void RemoveFlag(uint64 flag) { info_ &= ~flag; }
  bool AtomicSetFlag(uint64 flag); // return the old flag value
  void SetLength(uint64 length) 
  { info_ = (info_ & 0xffffffull) | (length << 24); }
  uint64 GetLength() const { return info_ >> 24; }
  uint8 & LgAccessCountRef() const { // depends on little endian
    return (((uint8*)(&info_))[2]); }
  void SetLgAccessCount(uint8 val) { 
    LgAccessCountRef() = val; }
  uint64 NodeCount() { 
    if (GetType() == IMMUTABLE_ARRAY) return node_count_;
    return 1;
  }

  // Array accessors
  uint64 ArraySize() const { return GetLength(); }
  Thing* ImmutableArrayData() { 
    ThingType tt = GetType();
    if ((tt != IMMUTABLE_ARRAY) && (tt != SYMBOL)) {
      cout << "::ImmutableArrayData " << tt << endl;
      CHECK(false);
    }
    return (Thing*) (this + 1); }
  Thing* MutableArrayData() { 
    CHECK(GetType() == MUTABLE_ARRAY);
    return (Thing*) marray_data__; }
  Thing & ImmutableArrayRef(int i) { 
    CHECK(0 <= i);
    CHECK(i < (int64)GetLength());
    return ImmutableArrayData()[i]; }
  Thing & MutableArrayRef(int i) { 
    CHECK(0 <= i);
    CHECK(i < (int64)GetLength());
    CHECK(i < (int64)marray_capacity__);
    return MutableArrayData()[i]; }
  Thing & Ref(int i) {
    if (IsMutable()) return MutableArrayRef(i);
    return ImmutableArrayRef(i);
  }

  // Simple checks and modifiers
  bool IsMutable() { return (GetType() == MUTABLE_ARRAY); }
  bool IsEqualToImmutableArray(Thing *contents, uint64 length);

  // various initializers
  void InitFreeSpace(uint64 length) {
    CHECK(length > 0) ; // if (length == g0) return;
    SetType(FREE_SPACE);
    SetLength(length); }
  void InitImmutableArray(uint64 id, Thing *data, uint64 length);
  void InitMutableArray();
  void InitSymbol(uint64 id, const string &data);
  void ReplaceWithFreeSpace() { InitFreeSpace(WordSize()); }
  Thing GlobalBoxToThing() { return Thing(id_); }
  Thing LocalBoxToThing() { return Thing(uint64(this)); }
};

bool BoxesHaveSameIDs(Box *b1, Box *b2);

// ------------- HASHING THINGS -------------------
inline uint64 ArrayContentHashStart() { return 0xdeadbeef12345678ull; }
inline uint64 ArrayContentHashNext(uint64 last_hash, Thing new_element) {
  return Fingerprint(new_element.ID(), last_hash); }
inline uint64 ArrayContentHash(Thing*a, uint64 length) {
  uint64 ret = ArrayContentHashStart();
  for (uint64 i=0; i<length; i++) ret = ArrayContentHashNext(ret, a[i]);
  return ret; }
inline uint64 HashStack(Thing* begin, Thing* end) {
  return ArrayContentHash(begin, end - begin); }
// Return a 60-bit hash of a thing array as a thing. 
inline Thing HashToThing(Thing *begin, uint64 length) {
  uint64 ret = ArrayContentHash(begin, length);
  return Thing::MakeInteger(ret & 0xfffffffffffffffULL);
}
// ---------- Some random functions ----------

// Convert an array thing into a vector of chars
inline void ArrayThingToVectorChars(Thing o, vector<char> *v) {
  if (!o.IsArray()) return;
  Box *b = o.GetBox();
  for (uint64 c=0; c<b->ArraySize(); c++) {
    Thing e = b->Ref(c);
    if (e.IsInteger()) {
      v->push_back(e.GetInteger());
    } else if (e.IsChar()) {
      v->push_back(e.GetUnboxedValue());
    } else {
      v->clear();
      return;
    }
  }
}

// Using the link_ field as a list
// Not thread safe
// A box can be in at most one list.
bool BoxListPush(Box **head, Box *b); 
Box * BoxListPop(Box **head);
inline Box * BoxListEnd() { return (Box *)0x1; }
void BoxListDisplay(Box *head);
void BoxListShoveHeadAfter(Box **head, Box *target);

void SortMArray(int64 width, Thing a);

inline bool IsArrayOfSize(Thing a, uint64 size) {
  if (!a.IsArray()) return false;
  if (a.ArraySize() != size) return false;
  return true;
}

inline bool IsArrayOfWidth(Thing a, uint64 width) {
  if (!a.IsArray()) return false;
  Box * ab = a.GetBox();
  for (uint64 i=0; i<ab->ArraySize(); i++) {
    Thing p = ab->Ref(i);
    if (!p.IsArray()) return false;
    if (p.ArraySize() != width) return false;
  }
  return true;
}

inline bool ContainsDirectArrays(Thing * contents, uint64 length) {
  for (uint64 i=0; i<length; i++) {
    Thing t = contents[i];
    if (t.IsDirect()) return true;
  }
  return false;
}

// Where to look for a box for Box by ID
inline Box ** BoxResolution(uint64 id, uint64 trial) {
  uint64 pos = HashTrialPosition (id >> 3, trial);
  return G_BOX_INDEX + (pos & G_BOX_INDEX_MASK);
}

// returns the old integer value of *p. coerces NULL into 0
inline int64 SyncFetchAddIntegerThing (Thing* p, int64 increment) {
  while (1) {
    Thing old_val = *p;
    if (!old_val.data_) {
      if (__sync_bool_compare_and_swap((uint64 *)p, 
				       old_val.data_, 
				       Thing::MakeInteger(increment).data_)){
	return 0;
      }
    } else if (old_val.GetBasicType() == INTEGER) {
      if (__sync_bool_compare_and_swap
	  ((uint64 *)p, 
	   old_val.data_, 
	   Thing::MakeInteger(old_val.GetInteger() + increment).data_)) {
	return old_val.GetInteger();
      }
    } else return 0;
  }
}

// Convert to an escaped string (readable back in)
string ToString(Thing p);
string ToStringShort(Thing p);
string StringToCPPString(Thing p);

// turns NULL pointer into NULL thing
inline Thing ThingPtrToThing(const Thing * p) {
  if (p) return *p;
  return NULL; }

inline Thing ThingToDoubleThing(Thing t) {
  switch (t.GetType()) {
  case INTEGER:
    return Thing::MakeDouble(t.GetInteger());
  case DOUBLE:
    return t;
  default:
    return NULL;
  }
}

inline Thing ThingToIntThing(Thing t) {
  if (t.IsBoxed()) return NULL;
  switch (t.GetType()) {
  case INTEGER:
    return t;
  case DOUBLE: {
    double d = t.GetDouble();
    if (finite(d)) return Thing::MakeInteger(int64(d));
    return NULL;
  }
  default:
    return Thing::MakeInteger(t.GetUnboxedValue());
  }
}

inline Thing ThingPlus(Thing a, Thing b) {
  if (a.IsInteger() && b.IsInteger()) 
    return Thing::MakeInteger(a.GetInteger() + b.GetInteger());
  if (a.IsNumber() && b.IsNumber()) 
    return Thing::MakeDouble(a.GetDouble() + b.GetDouble());
  return NULL;
}
inline Thing ThingMinus(Thing a, Thing b) {
  if (a.IsInteger() && b.IsInteger()) 
    return Thing::MakeInteger(a.GetInteger() - b.GetInteger());
  if (a.IsNumber() && b.IsNumber()) 
    return Thing::MakeDouble(a.GetDouble() - b.GetDouble());
  return NULL;
}
inline Thing ThingTimes(Thing a, Thing b) {
  if (a.IsInteger() && b.IsInteger()) 
    return Thing::MakeInteger(a.GetInteger() * b.GetInteger());
  if (a.IsNumber() && b.IsNumber()) 
    return Thing::MakeDouble(a.GetDouble() * b.GetDouble());
  return NULL;
}
inline Thing ThingDivide(Thing a, Thing b) {
  if (a.IsInteger() && b.IsInteger()) 
    return Thing::MakeInteger(a.GetInteger() / b.GetInteger());
  if (a.IsNumber() && b.IsNumber()) 
    return Thing::MakeDouble(a.GetDouble() / b.GetDouble());
  return NULL;
}

inline ThingType Thing::GetType() const {
  ThingType tt = GetBasicType();
  switch (tt) {
  case UNKNOWN_BOXED:
  case DIRECT_ARRAY: return GetBox()->GetType();
  case INDIRECT_ARRAY: return IMMUTABLE_ARRAY;
  case UNKNOWN_UNBOXED: return ThingType((data_ >> 8) & 0xff);
  default:
    return tt;
  }
}



#endif
